package com.learn.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]]
 * such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
 *
 * Notice that the solution set must not contain duplicate triplets.
 *
 * Example 1:
 *
 * Input: nums = [-1,0,1,2,-1,-4]
 * Output: [[-1,-1,2],[-1,0,1]]
 * Explanation:
 * nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
 * nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
 * nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
 * The distinct triplets are [-1,0,1] and [-1,-1,2].
 * <b>
 * Notice that the order of the output and the order of the triplets does not matter.
 * </b>
 * Example 2:
 *
 * Input: nums = [0,1,1]
 * Output: []
 * Explanation: The only possible triplet does not sum up to 0.
 * Example 3:
 *
 * Input: nums = [0,0,0]
 * Output: [[0,0,0]]
 * Explanation: The only possible triplet sums up to 0.
 * Constraints:
 *
 * 3 <= nums.length <= 3000
 * -105 <= nums[i] <= 105
 * Related Topics
 * 数组
 * 双指针
 * 排序
 *
 * 👍 6354
 * 👎 0
 */
public class num_15 {
    public static void main(String[] args) {
        // int[] nums = { -1, 0, 1, 0 };
        int[] nums = { -1, 0, 1, 2, -1, -4 };
        System.out.println(threeSum(nums));
    }

    public static List<List<Integer>> threeSum1(int[] nums) {
        ArrayList<List<Integer>> lists = new ArrayList<>();

        if (nums == null || nums.length < 3) {
            return lists;
        }
        HashSet<Integer> negative = new HashSet<>();
        HashSet<Integer> positive = new HashSet<>();
        int ZERO = 0;
        int zeroCount = 0;
        for (int num : nums) {
            if (num > 0) {
                positive.add(num);
            } else if (num < 0) {
                negative.add(num);
            } else {
                zeroCount++;
            }
        }
        if (negative.isEmpty() && zeroCount < 3) {
            return lists;
        }
        if (zeroCount >= 3) {
            lists.add(Arrays.asList(0,0,0));
        }
        if (positive.size() > 0 && negative.size() > 0) {

        }


        return lists;
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        ArrayList<List<Integer>> lists = new ArrayList<>();

        if (nums == null || nums.length < 3) {
            return lists;
        }
        Arrays.sort(nums);
        if (nums[0] > 0) {
            return lists;
        }

        // version-4
        for (int i = 0; i < nums.length - 2 && nums[i] <= 0; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int begin = i + 1;
            int end = nums.length - 1;
            while (begin < end) {
                if (nums[begin] + nums[end] == -nums[i]) {
                    lists.add(Arrays.asList(nums[begin], nums[end], nums[i]));
                    while (begin < end && nums[begin] == nums[begin + 1]) {
                        begin++;
                    }
                    while (begin < end && nums[end] == nums[end - 1]) {
                        end--;
                    }
                    begin++;
                    end--;
                } else if (nums[begin] + nums[end] < -nums[i]) {
                    begin++;
                } else {
                    end--;
                }
            }
        }
        return lists;
    }

    public static List<Integer> judge(int[] nums, int i, int j, int k) {
        if (nums[i] + nums[k] + nums[j] == 0) {
            return Arrays.asList(i, j, k);
        }
        return null;
    }

    //废弃版本代码
    // version-1
    // int i = 0;
    // int j = 1;
    // while (j < nums.length - 1) {
    //     for (int k = j + 1; k < nums.length; k++) {
    //         List < Integer > judge = judge(nums, i, j, k);
    //         if (judge != null) {
    //             lists.add(judge);
    //         }
    //     }
    //     i++;
    //     j++;
    // }
    // version-2
    // for (int i = 0; i < nums.length - 2; i++) {
    //     // int j=i+1;
    //     // int k=i+2;
    //     for (int j = i + 1, k = i + 2; k < nums.length; j++, k++) {
    //         System.out.println(judge(nums, i, j, k));
    //     }
    // }
    // version-3
    // Arrays.sort(nums);
    // for (int num = 0; num < nums.length; num++) {
    //     for (int i =  1, j = 2; j < nums.length; i++, j++) {
    //         if (-nums[num] == nums[i] + nums[j]) {
    //             Integer[] ints = { nums[num], nums[i], nums[j] };
    //             Arrays.sort(ints);
    //             List<Integer> list = Arrays.asList(ints);
    //             if (!lists.contains(list)) {
    //                 lists.add(list);
    //             }
    //         }
    //     }
    // }
}
